package com.hqq.search.symbol_table;

import com.hqq.search.OrderedKeyMap;

import java.util.Iterator;

/**
 * BinarySymbolTableSearch
 * 基于数组的二分查找的符号表实现
 * Created by heqianqian on 2017/8/5.
 */
public class BinarySymbolTableSearch<K extends Comparable<K>, V> implements OrderedKeyMap<K, V> {

    private static final int DEFAULT_CAPACITY = 10;

    private K[] keys;

    private V[] values;

    private int size;

    public BinarySymbolTableSearch() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public BinarySymbolTableSearch(int capacity) {
        keys = (K[]) new Comparable[capacity];
        values = (V[]) new Comparable[capacity];
    }

    @Override
    public void put(K key, V value) {
        int i = rank(key);
        //若键存在就更新值
        if (i < this.size && keys[i].compareTo(key) == 0) {
            values[i] = value;
        } else {//否则创建新的元素
            for (int j = size; j > i; j--) {
                //键值后移
                keys[j] = keys[j - 1];
                values[j] = values[j - 1];
            }
            //插入元素
            keys[i] = key;
            values[i] = value;
            //元素个数+1
            this.size++;
        }
    }

    @Override
    public V get(K key) {
        if (isEmpty()) {
            return null;
        }
        int i = rank(key);
        if (i < this.size && keys[i].compareTo(key) == 0) {
            return values[i];
        }
        return null;
    }

    @Override
    public void delete(K key) {
        remove(rank(key));
        System.out.println("index="+rank(key));
    }

    private void remove(int index) {
        for (int i = index; i < size - 1; i++) {
            keys[i] = keys[i + 1];
            values[i] = values[i + 1];
        }
        this.size--;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<K> iterator(K low, K high) {
        return new BinarySTSearchIterator(this, rank(low), rank(high));
    }

    @Override
    public K max() {
        return keys[this.size - 1];
    }

    @Override
    public K min() {
        return keys[0];
    }

    /**
     * 返回表中小于key的键的数量[二分查找]
     * 基于非递归实现
     */
    @Override
    public int rank(K key) {
        int low = 0, high = size;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) {//要查找的值小于中间值
                high = mid - 1;
            } else if (cmp > 0) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return low;
    }

    /**
     * 返回表中小于key的键的数量[二分查找]
     * 基于递归实现
     */
    private int rank(K key, int low, int high) {
        if (high < low) {
            return low;
        }
        int mid = low + (high - low) / 2;
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) {
            return rank(key, low, mid - 1);
        } else if (cmp > 0) {
            return rank(key, mid + 1, high);
        }
        return mid;
    }

    @Override
    public K select(int k) {
        return keys[k];
    }

    public K[] getKeys() {
        return keys;
    }

    public V[] getValues() {
        return values;
    }


    private class BinarySTSearchIterator implements Iterator<K> {

        private BinarySymbolTableSearch<K, V> table;

        private int low;

        private int high;

        public BinarySTSearchIterator(BinarySymbolTableSearch<K, V> table, int low, int high) {
            this.table = table;
            this.low = low;
            this.high = high;
        }

        @Override
        public boolean hasNext() {
            return low != high;
        }

        @Override
        public K next() {
            return table.keys[low++];
        }
    }
}
